package item04;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Lv Jing
 * @date 2018年07月11日 0:11
 */
public class TwoDimensionArr {

    /*
    题目：二维数组的行从左到右依次增大，列从上到下依次增大，指定一个数，查找是否在数组中存在。
    思路：一个数，在数组中找一个中间位置的数比较，如果比该数大，则输入的数可能在这个数的右边或下面；如果比这个数小，就可能在
    它的上面或左面。这样无法判断到底是在左面还是上面，维度过多，所以可以用右上角的数作为基准判断，比它大的数肯定在它的下面，
    比它小的数肯定在它的左边。
     */

    private boolean isExistInArr(int[][] arr, int expect) {
        if (arr == null) {
            return false;
        }
        int rows = arr.length;
        if (rows == 0) {
            return false;
        }
        int columns = arr[0].length;
        if (columns == 0) {
            return false;
        }

        int row = 0;
        int column = columns -1;

        while (row < rows && column >= 0) {
            int value = arr[row][column];
            // 相等的数，则直接返回
            if (expect == value) {
                return true;
            }
            // 比所选位置的数大，则在其下方
            if (expect > value) {
                row++;
            }
            // 比所选位置的数小，则在其左方
            if (expect < value) {
                column--;
            }
        }
        return false;
    }

    /**
     * 非法输入。空数组
     */
    @Test
    public void test01() {
        Assert.assertFalse(isExistInArr(null, 1));
    }

    /**
     * expect比指定数组的最大值大
     */
    @Test
    public void test02() {
        int[][] arr = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        Assert.assertFalse(isExistInArr(arr, 16));
    }

    /**
     * expect比指定数组的最小值小
     */
    @Test
    public void test03() {
        int[][] arr = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        Assert.assertFalse(isExistInArr(arr, 0));
    }

    /**
     * expect在指定数组的最大值和最小值中间，但不存在
     */
    @Test
    public void test04() {
        int[][] arr = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        Assert.assertFalse(isExistInArr(arr, 3));
    }

    /**
     * expect为指定数组的最小值
     */
    @Test
    public void test05() {
        int[][] arr = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        Assert.assertTrue(isExistInArr(arr, 1));
    }

    /**
     * expect为指定数组的最大值
     */
    @Test
    public void test06() {
        int[][] arr = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        Assert.assertTrue(isExistInArr(arr, 15));
    }

    /**
     * expect在指定数组的最大值和最小值中间，且存在
     */
    @Test
    public void test07() {
        int[][] arr = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        Assert.assertTrue(isExistInArr(arr, 12));
    }
}
